#include <iostream>
using namespace std;

struct TreeLinkNode {
    TreeLinkNode *left;
    TreeLinkNode *right;
    TreeLinkNode *next;
    int val;

    TreeLinkNode(int _val){
        left = NULL;
        right = NULL;
        next = NULL;
        val = _val;
    }
};

void LinkNext(TreeLinkNode *root, TreeLinkNode *cur, int depth, unsigned int pathCode){
    while((pathCode>>depth) ==0){
        // still possible have next, follow a code
        int tmpDepth = depth;
        unsigned int tmpCode = pathCode;
        TreeLinkNode *curPoint = root;      
        while(tmpDepth > 0 && curPoint){
            int leftRight = tmpCode & (0x1<<(tmpDepth-1));
            if(leftRight==0){
                // left
                curPoint = curPoint->left;
            }
            else{
                curPoint = curPoint->right;
            }
            --tmpDepth;
        }
        ++pathCode;
        if(!curPoint){
            // invalid code
            continue;
        }
        else{
            // find next
            cur->next = curPoint;
            cur = cur->next;
            return;
        }
    }
}

void DFS(TreeLinkNode *root, TreeLinkNode *cur, int depth, unsigned int code){
    if(!cur)
        return;
    LinkNext(root, cur, depth, code+1);
    if(cur->left){
        DFS(root, cur->left, depth+1, code<<1);
    }
    if(cur->right){
        DFS(root, cur->right, depth+1, (code<<1)+1);
    }
}


void connect(TreeLinkNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function

    DFS(root, root, 0, 0x0);
}


void ConnectNext(TreeLinkNode *parent, TreeLinkNode *cur){
    TreeLinkNode *curParent = parent;
    TreeLinkNode *opt = NULL;
    if(parent->left == cur){
        opt = parent->right;
    }
    while(!opt && curParent){
        if(opt == curParent->left){
            opt = curParent->right;
        }
        else{
            curParent = curParent->next;
            opt = curParent->left;
        }
    }
    cur->next = opt;
    // link child
    if(cur->right)
        ConnectNext(cur, cur->right);
    if(cur->left)
        ConnectNext(cur, cur->left);

}

void connect1(TreeLinkNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(!root)
        return;
    if(root->left && root->right)
        root->left->next = root->right;
    if(root->right)
        ConnectNext(root, root->right);
    if(root->left)
        ConnectNext(root, root->left);

}




int main(){
    TreeLinkNode root(0);
    TreeLinkNode a(1);
    TreeLinkNode a1(3);
    TreeLinkNode a2(4);
    //   a.left = &a1;
    //   a.right = &a2;
    root.left = &a;
    TreeLinkNode b(2);
    TreeLinkNode b1(5);
    TreeLinkNode b2(6);
    //    b.left = &b1;
    //   b.right = &b2;
    root.right = &b;

    connect(&root);


    return 0;
}